package com.lun.swordtowardoffer2.c01;

public class CountBits {

	//1. 简单计算每个整数的二进制形式中1的个数
	public int[] countBits(int num) {
		int[] result = new int[num + 1];

		for (int i = 0; i <= num; ++i) {
			int j = i;
			while (j != 0) {
				result[i]++;
				j = j & (j - 1);
			}
		}

		return result;
	}
	
	public int[] countBits_(int num) {
		int[] result = new int[num + 1];
		
		for (int i = 0; i <= num; ++i) {
			int j = i;
			while (j != 0) {
				if((j & 1) == 1)
					result[i]++;
				j >>= 1; 
			}
		}		
		return result;
	}

	//2. 根据“i & (i - 1)”计算i的二进制形式中1的个数
	public int[] countBits2(int num) {
		int[] result = new int[num + 1];
		for(int i = 1; i <= num; i++) {
			result[i] = result[i & (i - 1)] + 1;
		}

		return result;
	}

	//3. 根据“i/2”计算i的二进制形式中1的个数
	public int[] countBits3(int num) {
		int[] result = new int[num + 1];
		for(int i = 1; i <= num; i++) {
			result[i] = result[i >> 1] + (i & 1);
		}
		return result;
	}

}
